import java.io.*;
import java.util.Vector;
import java.util.List;
import java.util.Comparator;
import java.util.Collections;

public class Graph {

  Vector<String> words = new Vector<String>(); //list of words(strings)
  Vector<Node> nodes = new Vector<Node>(); //list of nodes
  Vector<Connection> connections = new Vector<Connection>(); //list of edges
  int nextMaxLink = 0; //used to keep track of set of max connections
  int num_max;
  int num_equal_conflicts;

  public Graph(String filename) {
    try {
      // Open the file that is the first 
      // command line parameter
      FileInputStream fstream = new FileInputStream(filename);
      // Get the object of DataInputStream
      DataInputStream in = new DataInputStream(fstream);
      BufferedReader br = new BufferedReader(new InputStreamReader(in));
      String strLine;
      //Read File Line By Line
      System.out.println("Reading words:");
      while ((strLine = br.readLine()) != null) {
        // Print the content on the console
        words.add(strLine);
        nodes.add(new Node(strLine));
        //numVertices++;
        System.out.println(strLine);
      }
      System.out.println("There are " + nodes.size() + " words.");
      //Close the input stream
      in.close();
    } catch (Exception e) {
      System.err.println("Error: " + e.getMessage());
      System.exit(-1);
    }
  }

  Vector<String> getWords() {
    return this.words;
  }

  /*
   * returns length of longest suffix of 'a' which is also a prefix of 'b'
   */
  int score(String a, String b) {
    // assume words are arranged in given order (ab)
    int max_length = Math.min(a.length(), b.length());
    for (int i = max_length; i >= 1; i--) {    // check if i characters match
      String a_part = a.substring(a.length() - i, a.length());
      String b_part = b.substring(0, i);
      if (a_part.equals(b_part)) {
        return i;
      }
    }
    return 0;
  }

  /*
   * Sort our connections by score in descending order
   */
  void sortConnections() {
    final Comparator<Connection> comp = new Comparator<Connection>() {

      @Override
      public int compare(Connection a, Connection b) {
        return -(a.getValue() - b.getValue());
      }
    };

    Collections.sort(connections, comp);
  }

  /*
   * Sort connections that have equal max score by conflicts in ascending order
   */
  void sortConnectionsByConflicts() {
    final Comparator<Connection> comp = new Comparator<Connection>() {

      @Override
      public int compare(Connection a, Connection b) {
        return a.getConflicts() - b.getConflicts();
      }
    };

    List<Connection> maxConnections = connections.subList(0, num_max);
    Collections.sort(maxConnections, comp);
  }

  /*
   * Sort connections that have equal min conflicts by word length in ascending order
   */
  void sortConnectionsByLength() {
    final Comparator<Connection> comp = new Comparator<Connection>() {

      @Override
      public int compare(Connection a, Connection b) {
        return a.getLength() - b.getLength();
      }
    };

    List<Connection> conflictConnections = connections.subList(0, num_equal_conflicts);
    Collections.sort(conflictConnections, comp);
  }

  /*
   * 
   */
  void sortConnectionsByNextBest(int start, int end) {
    
    for(Connection c : connections.subList(start, end)) {
      Node[] nodes = new Node[]{c.getFromNode(), c.getToNode()};
      for (Node n : nodes)
      {
        final Comparator<Integer> comp1 = new Comparator<Integer>() {
          @Override
          public int compare(Integer a, Integer b) {
            return -(a-b); // descending
          }
        };
        Collections.sort(n.connectionScores, comp1);
      }
    }
    
    final Comparator<Connection> comp = new Comparator<Connection>() {
      @Override
      public int compare(Connection a, Connection b) {

        return -(a.getFitness() - b.getFitness());
      }
    };

    List<Connection> conflictConnections = connections.subList(start, end);
    Collections.sort(conflictConnections, comp);
  }

  int makeGraph() {
    int s;
    nextMaxLink = 0;
    connections.clear(); //clear edge list for rebuilding
    for (int i = 0; i < nodes.size(); i++) {
      nodes.get(i).pconflicts = 0;
      nodes.get(i).sconflicts = 0;
    }
//Creating all connections with current list of nodes
    for (int cur = 0; cur < nodes.size(); cur++) {
      for (int c = cur + 1; c < nodes.size(); c++) {
        Node cur_node = nodes.elementAt(cur);
        Node compare_node = nodes.elementAt(c);
        
        s = score(cur_node.getWord(), compare_node.getWord());
        connections.add(new Connection(cur_node, compare_node, s));
        cur_node.connectionScores.add(s);
        compare_node.connectionScores.add(s);       
        //Combined Conflict & Fitness Heuristic
        if (s > 0) {
          cur_node.sconflicts += s;
          compare_node.pconflicts += s;
        }
        
        s = score(compare_node.getWord(), cur_node.getWord());
        connections.add(new Connection(compare_node, cur_node, s));
        cur_node.connectionScores.add(s);
        compare_node.connectionScores.add(s);
        //Conflict Fitness Heuristic
        if (s > 0) {
          cur_node.pconflicts += s;
          compare_node.sconflicts += s;
        }
      }
    }

    optimizeGraph();

    return 0;
  }

  /*
   * Optimize the graph by applying heuristics
   */
  void optimizeGraph() {
    sortConnections();              // sort by score
    findNumMaxConnections();
    sortConnectionsByConflicts();
    findNumEqualConflicts();
    
    /* we have two heuristics to choose from */
    //sortConnectionsByLength();
    //sortConnectionsByNextBest(0, num_max);
  }

  void printConnection(Connection c) {
    System.out.println(c.getFromNode().getWord() + " : " + c.getToNode().getWord()
            + ", s = " + c.getValue() + ", c = " + c.getConflicts());
  }

  void printConnections() {
    System.out.println("Printing Connections:");
    for (Connection c : connections) {
      printConnection(c);
    }
  }

  /*
   * Finds the number of connections that have max score
   */
  void findNumMaxConnections() {
    int maxscore = connections.elementAt(0).getValue();
    num_max = 0;
    while (num_max < connections.size() && connections.elementAt(num_max).getValue() == maxscore) {
      num_max++;
    }
  }

  /*
   * Finds the number of connections that have min conflicts
   */
  void findNumEqualConflicts() {
    int conflicts = connections.elementAt(0).getConflicts();
    num_equal_conflicts = 0;
    while (num_equal_conflicts < num_max
            && connections.elementAt(num_equal_conflicts).getConflicts() == conflicts) {
      num_equal_conflicts++;
    }
  }

  /*
   * selects a connection that has maximal score that has not been used yet
   */
  Connection findMaxValue() {
    while (nextMaxLink < num_max) {
      if (connections.elementAt(nextMaxLink).getFromNode().sused == false
              && connections.elementAt(nextMaxLink).getFromNode().pused == false
              && connections.elementAt(nextMaxLink).getToNode().pused == false
              && connections.elementAt(nextMaxLink).getToNode().sused == false) {
        return connections.elementAt(nextMaxLink++);
      }
      nextMaxLink++;
    }
    //If run out of connections in the Max set, redo the graph and then recurse
    redoGraph();
    return findMaxValue();
  }

  /*
   * Combines two word nodes into one node
   */
  void joinWords(Node from, Node to, int value) {
    Node combined = new Node(from.getWord() + to.getWord().substring(value));
    combined.addNode(from);
    combined.addNode(to);
    combined.pconflicts = from.pconflicts;
    combined.sconflicts = to.sconflicts;
    nodes.add(combined);

    from.sused = to.pused = true;
    nodes.remove(from);
    nodes.remove(to);
  }

  void redoGraph() {
    makeGraph();
  }
}
